package com.salim.leetcode.$31;

import java.util.Arrays;

public class NextPermutation {
    public void nextPermutation(int[] nums) {
        int swapLeft = -1;
        int swapRight = -1;

        for(int i=nums.length-1;i>=0;i--){
            if(i-1>=0){
                if(nums[i-1]>=nums[i]){
                    continue;
                }else{
                    swapLeft = i-1;
                    break;
                }
            }else{
                swap(nums,0,nums.length-1);
                return;
            }
        }

        for(int i = swapLeft + 1;i<nums.length;i++){
            if(i+1<nums.length){
                if(nums[i+1]<=nums[swapLeft] && nums[i]>=nums[swapLeft]){
                    swapRight = i;
                    break;
                }
            }else{
                swapRight = i;
            }
        }

        int middle = nums[swapLeft];
        nums[swapLeft] = nums[swapRight];
        nums[swapRight] = middle;
        swap(nums,swapLeft + 1,nums.length-1);
    }

    public void swap(int[] nums,int start,int end) {
        int temp;
        while (start<=end){
            temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }


    public static void main(String[] args){
        NextPermutation nextPermutation = new NextPermutation();
        int[] nums = {1,5,1};
        nextPermutation.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }


}
